/**
 * This class contains the rest of the implementation of the
 * matrix operations, in this case for the sparse representation.
 * 
 * Representational invariants:
 * The entries of the matrix are stored in linked list nodes.  The
 * nodes belong to the linked lists for its row and column in order
 * from left to right row-wise and top to bottom column-wise.  Only
 * non-zero matrix values are stored in nodes, and no zero values
 * are stored; the absence of a node at a particular coordinate pair
 * is assumed to represent zero. 
 * 
 * !!!!! Do not add any additional public or protected methods
 * or variables to this class.  You may add any PRIVATE variables
 * or methods as you see necessary, but do not add any additional
 * major data structures. !!!!!
 */

public class SparseMatrix extends AbstractMatrix
{
	
	/* The heads of the lists starting at each row and column */
	private Node[] rowList, colList;
	
	/**
	 * findNode -- will find the address of the node by the given row and col
	 * @param row specific row
	 * @param col specific col
	 * @return return null pointer if node cannot find, or return the address of that node
	 */
	private Node findNode(int row, int col){
		Node rowN, colN;
		// check validation of the row , col
		if (row < 0 || row >= this.getRows() || col < 0 || col >= this.getCols())
			throw new IllegalArgumentException("invalid row or col!!");
		
		// we will search from both row and col, to see who get the node first, or Null
		rowN = rowList[row];
		colN = colList[col];
		
		while (true){
			// Check the row first:
			// a exist node should be pointed by both row and col 
			if (rowN == null)
				return null;
			
			if (rowN.getRow() == row && rowN.getCol() == col){
				return rowN;
			}
			rowN = rowN.getColNext();
			//////////////////////////////////////////////////////////
			
			// check the col then
			// the process is similar 
			if (colN == null)
				return null;
			
			if (colN.getRow() == row && colN.getCol() == col){
				return colN;
			}
			colN = colN.getRowNext();
		}
		
		
		// should not get here
		
	}
	
	
	public void clear()
	{
		rowList = new Node[this.getRows()];
		for (int row=0; row < this.getRows(); row++){
			rowList[row] = null;
		}
		
		colList = new Node[this.getCols()];
		for (int col=0; col < this.getCols(); col++){
			colList[col] = null;
		}
	
		//throw new RuntimeException("You must implement this method!");
	}
	
	public double get(int row, int col)
	{
		Node tmp = this.findNode(row, col);
		
		if (tmp == null){
			return 0.0;
		}
		
		return tmp.getData();
		//throw new RuntimeException("You must implement this method!");
	}
	
	public void set(int row, int col, double val)
	{
		Node tmp = this.findNode(row, col);
		// if the node exists, we just overwrite its value
		if (tmp != null){
			tmp.setData(val);
			return;
		}
		
		// else we has to create a new node, then insert it into both rowList and colList
		Node node = new Node(row, col, val);
		
		// First insert into the rowList
		// linklist is empty
		if (rowList[row] == null){
			rowList[row] = node;
		}
		// insert node at the very beginning
		else if (rowList[row].getCol() > col){
			node.setColNext(rowList[row]);
			rowList[row] = node;
		}
		else if (rowList[row].getCol() < col){
			tmp = rowList[row];
			while (true){
				// insert node at the end of the linklist
				if (tmp.getColNext() == null){
					tmp.setColNext(node);
					break;
				}
				
				// insert node at the middle of the linklist
				if (tmp.getColNext().getCol() > col){
					node.setColNext(tmp.getColNext());
					tmp.setColNext(node);
					break;
				}
				// go to the next node
				else if (tmp.getColNext().getCol() < col){
					tmp = tmp.getColNext();
				}
				else{
					throw new RuntimeException("node already exists at rowlist when trying to insert a node");
				}
			}
		}
		else{
			throw new RuntimeException("node already exists at rowlist when trying to insert a node");
		}
		
		// Second, we do the same thing for the colList
		// linklist is empty
		if (colList[col] == null){
			colList[col] = node;
		}
		// insert node at the very beginning
		else if (colList[col].getRow() > row){
			node.setRowNext(colList[col]);
			colList[col] = node;
		}
		else if (colList[col].getRow() < row){
			tmp = colList[col];
			while (true){
				// insert node at the end of the linklist
				if (tmp.getRowNext() == null){
					tmp.setRowNext(node);
					break;
				}
				
				// insert node at the middle of the linklist
				if (tmp.getRowNext().getRow() > row){
					node.setRowNext(tmp.getRowNext());
					tmp.setRowNext(node);
					break;
				}
				// go to the next node
				else if (tmp.getRowNext().getRow() < row){
					tmp = tmp.getRowNext();
				}
				else{
					throw new RuntimeException("node already exists at collist when trying to insert a node");
				}
			}
		}
		else{
			throw new RuntimeException("node already exists at collist swhen trying to insert a node");
		}
		
		
		//throw new RuntimeException("You must implement this method!");
	}
	
	public double[] getRow(int row)
	{
		// check the validation
		if (row < 0 || row >= this.getRows())
			throw new IllegalArgumentException("invalid row for getRow!!");
		
		// deep copy a array to return
		double[] rowArray = new double[this.getCols()];
		
		for (int col=0; col < this.getCols(); col++){
			rowArray[col] = this.get(row, col);
		}
		
		return rowArray;
		//throw new RuntimeException("You must implement this method!");
	}
	
	public double[] getCol(int col)
	{
		// check the validation 
		if (col < 0 || col >= this.getCols())
			throw new IllegalArgumentException("invalid col for getCol!!");
		
		// deep copy a array to return
		double[] colArray = new double[this.getRows()];
		
		for (int row=0; row < this.getRows(); row++){
			colArray[row] = this.get(row, col);
		}
		
		return colArray;
		//throw new RuntimeException("You must implement this method!");
	}
	
	public double rowSum(int row)
	{
		// check the validation
		if (row < 0 || row >= this.getRows())
			throw new IllegalArgumentException("invalid row for getRow!!");
		
		double sum = 0.0;
		
		for (int col=0; col < this.getCols(); col++){
			sum = sum + this.get(row, col);
		}
		
		return sum;
		//throw new RuntimeException("You must implement this method!");
	}
	
	public double colSum(int col)
	{
		// check the validation 
		if (col < 0 || col >= this.getCols())
			throw new IllegalArgumentException("invalid col for getCol!!");
		
		double sum = 0.0;
		
		for (int row=0; row < this.getRows(); row++){
			sum = sum + this.get(row, col);
		}
		
		return sum;
		//throw new RuntimeException("You must implement this method!");
	}
	
	public boolean checkRepresentation()
	{
		Node tmp;
		int  prev;
		
		// check whether data was stored from left to right at rows
		for (int row=0; row < this.getRows(); row++){
			tmp = rowList[row];
			// initialize prev
			prev = -1;
			while (true){
				if (tmp == null){
					break;
				}
				else{
					if (tmp.getCol() <= prev){
						return false;
					}
					prev = tmp.getCol();
					tmp = tmp.getColNext();
				}
			}
			
		}
		
		// check whether data was stored from top to bottom at cols
		prev = -1;
		for (int col=0; col < this.getCols(); col++){
			tmp = colList[col];
			// initialize prev
			prev = -1;
			while (true){
				if (tmp == null){
					break;
				}
				else{
					if (tmp.getRow() <= prev){
						return false;
					}
					prev = tmp.getRow();
					tmp = tmp.getRowNext();
				}
			}
		}
		
		
		// everything seems good, return true
		return true;
		//throw new RuntimeException("You must implement this method!");
	}

}
